//第一种方法使用最小堆
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <queue>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto compare = [](ListNode * a, ListNode * b) {
            return a->val>b->val;  // 使用 std::greater<int> 比较值
        };
        priority_queue<ListNode*, std::vector<ListNode*>, decltype(compare)> q(compare);
        //创建一个最小堆
        for(int i = 0;i<lists.size();i++)
        {
            if(lists[i])
            q.push(lists[i]);
        }
        ListNode* newhead = new ListNode(-1);
        ListNode* cur = newhead;
        while(!q.empty())//使用优先级队列来解决这道题目
        {
            ListNode* tmp = q.top();
            q.pop();
            if(tmp->next!=nullptr)
            {
                q.push(tmp->next);
            }
            cur->next = tmp;
            cur = cur->next;
        }
        return newhead->next;
    }
};
//第二种方法使用分治递归解决
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
     ListNode* merge(ListNode* left,ListNode* right)
     {
        ListNode* head = new ListNode(-1);
        ListNode* cur = head;
        while(left&&right)
        {
            if(left->val<right->val)
            {
                cur->next = left;
                left = left->next;
            }
            else
            {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        cur->next = left?left:right;
        ListNode* ret = head->next;
        delete head;
        return ret;
     }
     ListNode* mergesort(vector<ListNode*>& lists,int begin,int end)
     {
        int mid = end-begin;
        if(mid == 0)
        {
            //begin和end指向了同一个链表，不需要进行合并返回nullptr
            return nullptr;
        }
        if(mid == 1)
        {
            //begin和end指向了两个链表需要进行合并
            return lists[begin];
        }
        ListNode* left = mergesort(lists,begin,begin+mid/2);
        ListNode* right = mergesort(lists,begin+mid/2,end);//处理左边的数组和右边的数组
        //到这里需要将两个有序的链表合并为一个有序的链表
        //到这里左右就是两个已经划分好的链表了需要将这两个链表进行合并并且返回合并后的新头节点
        return merge(left,right);

     }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergesort(lists,0,lists.size());//这个函数的作用就是将list中的链表使用分治的方法不断合并

    }
};